/**
 * Shamirs secret sharing scheme
 *
 * This file also includes Lagrange Interpolation, doubleShareRandom,
 * GenerateTriples.
 *
 * Implemented by Kasper Damgård
 */

import java.util.*;
import java.math.*;
import java.security.*;
import org.jscience.mathematics.vector.*;
import org.jscience.mathematics.number.*;
import org.lsmp.djep.groupJep.values.Polynomial;
import org.lsmp.djep.groupJep.groups.Zn;

public class SharingProtocols{

    ArrayList<Integer> coefficients;
    private SecureRandom randGen;
    private int secret;
    int fieldSize = Utilities.F;
    Player p;    
    BigInteger[] beta;

    SharingProtocols(SecureRandom rand, Player p){
        coefficients = new ArrayList<Integer>();
        randGen = rand;        
        generateSecret();
        this.p = p;

        beta = new BigInteger[Utilities.n_prime+1];
        for(int i = 1; i<= Utilities.n_prime ; i++){
            beta[i] = BigInteger.valueOf(i);
        }
    }

    /**
     * @returns a secret number between 1 and fieldSize
     */
    public void generateSecret(){
        secret = randGen.nextInt(fieldSize);
        if(secret == 0){
            generateSecret();
        }
    }

    public void setSecret(int secret){
        this.secret = secret;
    }

    public int getSecret(){
        return secret;
    }

    /**
     * generateShares builds an array of BigIntegers containing a
     * function evaluation of f(j) for j = 1..n, where f is a "degree"
     * polynomial.
     * @returns a BigInteger array containing f(1)..f(n)
     */
    public BigInteger[] generateShares(int degree){
        //make sure arrayList is clear
        ArrayList<BigInteger> coefficients = new ArrayList<BigInteger>();
        BigInteger[] shares = new BigInteger[Utilities.n];

        for(int i = 0 ; i < degree ; i++){
            coefficients.add(BigInteger.valueOf(randGen.nextInt(fieldSize)));
        }

        for(int j = 1; j <= Utilities.n; j++){
            BigInteger sharing = BigInteger.valueOf(secret);
            BigInteger x_j = BigInteger.valueOf(j);
            int power = 1;
            for(BigInteger a : coefficients){
                sharing = sharing.add(a.multiply(x_j.pow(power)));
                power++;
                sharing = sharing.mod(Utilities.F_big); 
            }
            shares[j-1] = sharing;
        }
        return shares;
    }

    /**
     * @return A double-sharing of the same random secret.
     */
    public BigInteger[][] doubleShareRandom(int d1, int d2){                
        BigInteger[] share1 = generateShares(d1);
        BigInteger[][] doubleShare = new BigInteger[2][(share1.length+1)];

        for(int i = 0 ; i< share1.length ; i++){
            doubleShare[0][i+1] = share1[i];
        }
        BigInteger[] share2 = generateShares(d2);

        for(int i = 0 ; i< share2.length ; i++){
            doubleShare[1][i+1] = share2[i];
        }

        if(Utilities.DEBUG){
            //Testing phase:       
            HashMap<Integer, BigInteger> test1 = new HashMap<Integer, BigInteger>();
            HashMap<Integer, BigInteger> test2 = new HashMap<Integer, BigInteger>();
            for(int i = 1; i<= share1.length; i++){
                test1.put(i,share1[i-1]);
                test2.put(i,share2[i-1]);
            }
            BigInteger secret1 = lagrange(test1, d1, 0);
            BigInteger secret2 = lagrange(test2, d2, 0);
            if(!secret1.equals(secret2)){
                //We failed at doublesharing..
                System.err.println("Doublesharing FAILED... The two secrets are not the same!");
            }
            //end test phase
        }        

        return doubleShare;
    }

    /**
     * @returns the secret (i.e. f(0) ) given no corrupted
     * shares. Corruption must be handled by Berlekamp-Welch.
     */
    public BigInteger lagrange(HashMap<Integer, BigInteger> points, int degree, int point){        
        if(points.size() <= degree){
            System.out.println("Error! - number of points given does not exceed " + degree
                               + ". System returns -1...");
            try{
                throw new Exception();
            }
            catch(Exception e){
                e.printStackTrace();
            }
        }
        BigInteger secret = BigInteger.ZERO;
        int count = 0;
        for(Integer j : points.keySet()){
            //Only use degree+1 points. 
            if(count > degree) break;
            BigInteger y_j = points.get(j);            
            secret = secret.add(y_j.multiply(lagrangeBasis(j, points, degree, point))).mod(Utilities.F_big);
            count++;
        }   
        return secret;
    }

    private BigInteger lagrangeBasis(int j, HashMap<Integer, BigInteger> points, int degree, int point){
        BigInteger product = BigInteger.ONE;
        BigInteger x = BigInteger.valueOf(point);
        //run through degree+1 points in order to interpolate
        int count = 0;
        for(Integer m : points.keySet()){
            if(count > degree) break;
            if(m != j){
                BigInteger tmp = (BigInteger)Utilities.zn.div(x.subtract(BigInteger.valueOf(m)), 
                                                              BigInteger.valueOf(j-m).mod(Utilities.F_big));
                product = product.multiply(tmp).mod(Utilities.F_big);
            }
            count++;
        }
        return product;
    }

    /**
     * @returns the secret f(0) or -1 if player became unhappy
     * during the check.      
     */
    public BigInteger reconsPriv(int degree, HashMap<Integer, BigInteger> shares){        
        BigInteger secret;        
        if((Utilities.n_prime == (degree+Utilities.t_prime+1))
           || Utilities.n_prime <= (Utilities.t_prime*2+degree)){
            //n'=d+t'+1 OR n <= d+2t'- no BW, so all shares must lie on the polynomial
            for(Integer i : shares.keySet()){            
                if(!shares.get(i).equals(lagrange(shares, degree, i))){                    
                    p.setHappy(false);
                    return BigInteger.valueOf(-1);
                    //return lagrange(shares, degree, 0);
                }
            }
            secret = lagrange(shares, degree, 0);
        }
        else{
            Polynomial f = BW(degree, shares);
            secret = (BigInteger)f.getCoeff(0);
        }        
        return secret;
    }

    int nextRandomCorruption = 1;
    /**
     * Berlekamp-Welch algorithm. It finds the true polynomial even if
     * up to t of the shares are corrupted. It needs n>d+2t
     */
    public Polynomial BW(int degree, HashMap<Integer, BigInteger> shares){
        if(Utilities.n_prime <= (Utilities.t_prime*2+degree)){
            //Problem.. cannot do BW - must be an error
            System.err.println("ERROR - BW needs n>2t+d but this is not the case here.");
            System.err.println("n: " + Utilities.n_prime + ", 2t: "+ (2*Utilities.t_prime) + ", d: "+ degree);
            try{
                throw new Exception();
            }
            catch(Exception e){ 
                e.printStackTrace();
                System.exit(-1);
            }
        }
        
        try{
            //We assume all n' pairs of (x,y) is here
            ModuloInteger[][] elements_b = new ModuloInteger[Utilities.t_prime*2+degree+1][Utilities.t_prime*2+degree+1];
            ModuloInteger[][] elements_a = new ModuloInteger[Utilities.t_prime*2+degree+1][1];

            int count = 0;        
            for(Integer i : shares.keySet()){
                if(count == Utilities.t_prime*2+degree+1)
                    break;
                for(int j = 0; j <= (Utilities.t_prime+degree); j++){
                    //Filling out coefficients for B_j
                    BigInteger elem = BigInteger.valueOf(i).modPow(BigInteger.valueOf(j), Utilities.F_big);
                    elements_b[count][j] = new ModuloInteger(elem.intValue());
                } 
                for(int j = 0; j < Utilities.t_prime; j++){
                    //Filling out coefficients for A_j
                    BigInteger x_ij = BigInteger.valueOf(i).modPow(BigInteger.valueOf(j), Utilities.F_big);
                    BigInteger y_i = shares.get(i);
                    //remembering to negate the coeffs for A_j
                    BigInteger elem = y_i.multiply(x_ij).negate().mod(Utilities.F_big);
                    elements_b[count][j+Utilities.t_prime+degree+1] = new ModuloInteger(elem.intValue());
                }
                BigInteger x_it = BigInteger.valueOf(i).modPow(BigInteger.valueOf(Utilities.t_prime), Utilities.F_big);
                BigInteger y_i = shares.get(i);
                BigInteger a_it = y_i.multiply(x_it).mod(Utilities.F_big);
                elements_a[count][0] = new ModuloInteger(a_it.intValue());
                count++;
            }
            DenseMatrix<ModuloInteger> b_ij = DenseMatrix.valueOf(elements_b);
            DenseMatrix<ModuloInteger> a_ij = DenseMatrix.valueOf(elements_a);
        
            LUDecomposition<ModuloInteger> lu = LUDecomposition.valueOf(b_ij);
            //now we can solve for B_j and A_j:
            DenseMatrix<ModuloInteger> BA = lu.solve(a_ij);
        
            //Now we have all the info needed to construct the polynomials G and E:
            //B goes here and is listed first in BA
            BigInteger[] coeffs_G = new BigInteger[Utilities.t_prime+degree+1]; 
            //A goes here and is listed after the 2t+1 B's
            BigInteger[] coeffs_E = new BigInteger[Utilities.t_prime+1];
            for(int i = 0; i<= Utilities.t_prime+degree; i++){
                ModuloInteger b_j = BA.get(i,0);
                BigInteger b = BigInteger.valueOf(b_j.longValue());
                coeffs_G[i] = b;
            }
            for(int i = 0; i<Utilities.t_prime; i++){
                ModuloInteger a_j = BA.get(i+Utilities.t_prime+degree+1, 0);
                BigInteger a = BigInteger.valueOf(a_j.longValue());
                coeffs_E[i] = a;
            }
            coeffs_E[Utilities.t_prime] = BigInteger.ONE;

            Zn zn = new Zn(Utilities.F_big);
            Polynomial E = new Polynomial(zn, "x", coeffs_E);
            Polynomial G = new Polynomial(zn, "x", coeffs_G);

            if(G.getCoeffs().length < E.getCoeffs().length){
                //p.print("WARNING WARNING WARNING!!!! _ WTF. Can be saved if G is 0 polynomial");
                //p.print("G length: " + G.getCoeffs().length +", E length: " + E.getCoeffs().length);
                //p.print("G: " +G.toString());
                //p.print("E: " +E.toString());
                if(G.getCoeffs().length == 1 && G.getCoeff(0).equals(BigInteger.ZERO))
                    return G;
            }
            Polynomial f = G.div(E);

//             if(p.getID() == 2){
//                 p.print("");
//                 p.print("FINAL DIVIDED POLYNOMIAL:");
//                 p.print(f.toString());
//                 p.print("");
//             }

            return f;
        }
        catch(ArithmeticException e){
            //Not enough corrupted shares.. 
            
            int corruptions = 0;
            HashMap<Integer, BigInteger> temp = new HashMap<Integer, BigInteger>();
            temp.putAll(shares);
            for(Integer i : shares.keySet()){
                if(corruptions == Utilities.t_prime)
                    break;
                BigInteger corrupt = temp.remove(i);
                temp.put(i,corrupt.add(BigInteger.ONE).mod(Utilities.F_big));
                corruptions++;
            }
            return BW(degree, temp);
            
            /*
            HashMap<Integer, BigInteger> temp = new HashMap<Integer, BigInteger>();
            temp.putAll(shares);

            BigInteger corrupt = temp.remove(nextRandomCorruption);
            temp.put(nextRandomCorruption,corrupt.add(BigInteger.ONE).mod(Utilities.F_big));
            nextRandomCorruption = (nextRandomCorruption+1) % (Utilities.n_prime+1);
            if(nextRandomCorruption==0)
                nextRandomCorruption++;
            return BW(degree, temp);
            */
        }
    }

    public void reconsPubl(int degree, HashMap<Integer, BigInteger> shares, int caller, HashMap<Integer, MessageList> msgs){
        BigInteger[] u = new BigInteger[Utilities.n+1]; //careful here. u[0] == null...

        for(Integer j : p.players.keySet()){
            int power = 0;        
            BigInteger u_j = BigInteger.valueOf(0);
            for(Integer T : shares.keySet()){
                BigInteger temp = beta[j].modPow(BigInteger.valueOf(power), Utilities.F_big).multiply(shares.get(T));
                u_j = u_j.add(temp.mod(Utilities.F_big));
                power++;
            }
            u[j] = u_j.mod(Utilities.F_big);
        }                 

        //Now reconstruct [u_j] using ReconsPriv. - done by sending
        //shares around
        for(Integer i : p.players.keySet()){
            ArrayList<Object> list = new ArrayList<Object>();
            if(p.corrupt)
                list.add(u[i].add(BigInteger.ONE));
            else
                list.add(u[i]);
            list.add(shares.size()); //Amount of shares we want to reconstruct
            list.add(caller);
            //send this players part of u[i]
            if(msgs == null) //normal mode
                p.sendMessage(Utilities.reconsPubl, list, i);            
            else{
                //check mode
                int me = p.impersonate;
                MessageList ml = msgs.get(i);
                int c1 = ml.getMessageCounter(me);
                BigInteger s = (BigInteger)ml.getNextMsg(me);
                int c2 = ml.getMessageCounter(me);
                int d = (Integer)ml.getNextMsg(me); //what player i got from me
                if(!s.equals(u[i])){
                    p.faultDetected(me, i, u[i], s, c1);
                    return;
                }
                else if(d != shares.size()){
                    p.faultDetected(me, i, shares.size(), d, c2);
                    return;
                }
                else{
                    //check passed - go to next step which is reconsPriv
                    if(i == me)
                        p.receiveReconsPubl(s, d, me, caller, msgs);
                    else{
                        MessageList m = msgs.get(me);
                        BigInteger s1 = (BigInteger)m.getNextMsg(i);
                        int d1 = (Integer)m.getNextMsg(i);
                        p.receiveReconsPubl(s1, d1, i, caller, msgs);
                    }
                }
            }
        }
    }
    
    /**
     * Last step of ReconsPubl.
     * @returns all T s's which is now reconstructed and revealed to
     * all players. Takes any T (T-1)-consistent u's as input and
     * computes the s's.
     */
    public BigInteger[] computeSs(HashMap<Integer, BigInteger> us, int degree){
        BigInteger[] ss = new BigInteger[degree];
        //We now got the degree and the u's. Now do first lagrange to
        //get s_1:
        BigInteger s_recon = lagrange(us, degree-1, 0);
        ss[0] = s_recon;

        //Now, subtract s1 from the polynomial u(beta), and divide by beta.
        HashMap<Integer, BigInteger> us_ = new HashMap<Integer, BigInteger>();
        us_.putAll(us);
        for(int j = 2 ; j <= degree; j++){
            for(Integer i : us.keySet()){
                BigInteger tmp = (BigInteger)Utilities.zn.sub(us_.remove(i), s_recon);
                BigInteger u_ = (BigInteger)Utilities.zn.div(tmp, beta[i]);
                us_.put(i, u_);
            }
            s_recon = lagrange(us_, degree-j, 0);
            ss[j-1] = s_recon;
        }

        //Printing the reconstructed values:
        //p.print("The Reconstructed values are as follows: ");
        //for(int i = 0 ; i<ss.length; i++){
        //    p.print("s"+(i+1) + " = "+ ss[i]);
        //}

        return ss;
    }
    
}